lib/Mi manual de algoritmos/version_world_finals_2009/src/number_theory/bigmod.cpp

   1 //retorna (b^p)mod(m)
   2 // 0 <= b,p <= 2147483647
   3 // 1 <= m <= 46340
   4 int bigmod(int b, int p, int m){
   5   int mask = 1;
   6   int pow2 = b % m;
   7   int r = 1;
   8   while (mask){
   9     if (p & mask) r = (r * pow2) % m;
  10     pow2 = (pow2 * pow2) % m;
  11     mask <<= 1;
  12   }
  13   return r;
  14 }
  15 // Si se cambian los int por long longs los
  16 // valores de entrada deben cumplir:
  17 // 0 <= b,p <= 9223372036854775807
  18 // 1 <= m <= 3037000499
  19 // Si se cambian por unsigned long longs:
  20 // 0 <= b,p <= 18446744073709551615
  21 // 1 <= m <= 4294967295